package algorithm.leetcode.I1to100;

import java.util.Stack;

public class Q32 {

    // 有点像滑动窗口,i从左往右,j从i往左,时间复杂度为O(n^2),空间复杂度O(1)
    // 这个方法是 longestValidParentheses3 的来源
    public int longestValidParentheses(String s) {
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] count = new int[2];
            int index = i;
            for (int j = i; j >= 0; j--) {
                count[s.charAt(j)-40]++;

                // 检查
                if (count[1] == count[0]) maxLength = Math.max(maxLength, index-j+1);
                // 必须时刻保持右括号大于等于左括号(因为j是从i往左),否则重置数组
                else if (count[1] < count[0]) {
                    index = j-1;
                    count[0] = 0;
                    count[1] = 0;
                }
            }
        }
        return maxLength;
    }

    // 用栈,时间复杂度为O(n),空间复杂度O(n)
    public int longestValidParentheses2(String s) {
        int maxLength = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {
            // 对于遇到的每个左括号,将它的下标放入栈中
            if (s.charAt(i) == '(') stack.push(i);
            else {
                // 对于遇到的每个右括号,先弹出栈顶元素表示匹配了当前右括号
                stack.pop();
                // 如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
                if (stack.isEmpty()) stack.push(i);
                // 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
                maxLength = Math.max(maxLength, i-stack.peek());
            }
        }

        return maxLength;
    }

    public int longestValidParentheses3(String s) {
        int maxLeft = 0, maxRight = 0;
        int[] count = new int[2];

        // 正向循环,条件是左括号恒大于等于右括号
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)-40]++;
            // 检查
            if (count[1] == count[0]) maxLeft = Math.max(maxLeft, count[0]<<1);
            // 必须时刻保持左括号恒大于等于右括号,否则重置数组
            else if (count[1] > count[0]) {
                count[0] = 0;
                count[1] = 0;
            }
        }

        count = new int[2];
        // 逆向循环,条件是左括号恒小于等于右括号
        for (int i = s.length()-1; i >= 0; i--) {
            count[s.charAt(i)-40]++;
            // 检查
            if (count[1] == count[0]) maxRight = Math.max(maxRight, count[0]<<1);
            // 必须时刻保持左括号恒小于等于右括号,否则重置数组
            else if (count[1] < count[0]) {
                count[0] = 0;
                count[1] = 0;
            }
        }
        return Math.max(maxLeft, maxRight);
    }

    public static void main(String[] args) {
        Q32 q32 = new Q32();
        System.out.println(q32.longestValidParentheses3(")()())"));
    }
}
